package com.lry.basic.algorithm.bit;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/12/20
 */

public class SingleNumber {
    public static void main(String[] args) {
        System.out.println(new SingleNumber().singleNumber2(new int[]{1, 1, 2,2, 3}));
        System.out.println(new SingleNumber().singleNumber3(new int[]{1, 1, 1, 3}));
        int[] arr = new SingleNumber().singleNumber4(new int[]{1, 1, 2,2,103,2124});
        for (int i:arr) {
            System.out.println(i);
        }

    }

    //给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了2次。找出那个只出现了一次的元素。
    public int singleNumber2(int[] nums) {
        int  res = 0;
        for (int num:nums) {
            res^=num;
        }
        return res;
    }

    //给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
    public int singleNumber3(int[] nums) {
        int one = 0, two = 0, three;
        for (int num : nums) {
            // two的相应的位等于1，表示该位出现2次
            two |= (one & num);
            // one的相应的位等于1，表示该位出现1次
            one ^= num;
            // three的相应的位等于1，表示该位出现3次
            three = (one & two);
            // 如果相应的位出现3次，则该位重置为0
            two &= ~three;
            one &= ~three;
        }
        return one;
    }
    //给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素
    public int[] singleNumber4(int[] nums) {
        int  res = 0;
        for (int num:nums) {
            res^=num;
        }
        int rightestOne = rightestOne(res);
        int[] resArr = new int[2];
        for(int num:nums){
            if((num&rightestOne)!=0){
                resArr[0]^=num;
            }else{
                resArr[1]^=num;
            }
        }
        return resArr;
    }



    public int rightestOne(int num){
        int flag = 1;
        while(flag<Integer.MAX_VALUE){
            if((num&flag)!=0){
                return flag;
            }else{
                flag*=2;
            }
        }
        return -1;
    }
}
